package algorithm.difficult;

import pojo.ListNode;

import java.util.List;

public class reverseKGroup25 {
    public ListNode reverseKGroup(ListNode head, int k) {
        //总个数
        int n = 0;
        ListNode conut = head;
        while (conut != null) {
            n++;
            conut = conut.next;
        }
        //哨兵节点
        ListNode sentinel = new ListNode();
        sentinel.next = head;
        ListNode p0 = sentinel;
        ListNode p1 = head;
        ListNode pre = p0;
        ListNode cur = p1;
        //进行每组的翻转
        while (n > k) {
            n = n - k;
            //翻转
            for (int i = 0; i < k; i++) {
                ListNode temp = cur.next;
                cur.next = pre;
                pre = cur;
                cur = temp;
            }
            p0.next = pre;
            p1.next = cur;
            p0 = p1;
            p1 = cur;
        }
        return sentinel.next;
    }





    public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode sentinel = new ListNode();
        sentinel.next = head;
        //p0最后要指向right节点。即pre坐标
        ListNode p0 = sentinel ;
        for (int i = 0; i < left - 1; i++) {
            p0 = p0.next;
        }
        ListNode p1 = p0.next;
        //p1即left节点，要指向区间外的第一个节点，即cur坐标
        ListNode pre = p0;
        ListNode cur = p1;
        for (int i = left; i <=right ; i++) {
            System.out.println(cur.val);
            ListNode temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        //循环完毕
        p0.next = pre;
        p1.next = cur;
        return sentinel.next;
    }


    public ListNode reverseList(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode res = null;
        ListNode cur = head.next;
        ListNode pre = head;
        while (cur != null) {
            ListNode temp = cur;
            cur = cur.next;
            temp.next = pre;
            pre = temp;
        }
        return pre;
    }




}
